package gold.gold04;

import java.util.*;

/**
 * 一次 Comparator 的伟大实践
 * 题目中都是默认结果应该是升序, 也就是[3, 2, 1]我认为应该返回[-1, -1], 题目返回[0, 2], 不合适。
 */
public class S1616部分排序 {
    /**
     * 5, 好歹写出来了。
     * m, n位置上的点一定不在本来的位置上, 所以首位的大小关系一定可以确定整个序列的增减关系
     * 比如确定了是递增的, 如果找到了一个不递增的点, 那么前面每一个比他大的点都不能位置不变,
     * 也就是当前点插入到前面, 然后接着往后找, 可以用一个有序List
     */
    public static int[] subSort(int[] array) {
        if(array == null || array.length <= 2) return new int[]{-1, -1};
        int totalLen = array.length;
        // 自定义Comparator
        List<Integer> sortedArray = new ArrayList<>();
        Comparator<Integer> comparator;
        if(array[0] - array[totalLen - 1] < 0){
            comparator = new Comparator<Integer>(){
                @Override
                public int compare(Integer o1, Integer o2){
                    return o1 - o2;
                }
            };
        }else{
            comparator = new Comparator<Integer>(){
                @Override
                public int compare(Integer o1, Integer o2){
                    return o1 - o2;
                }
            };
        }

        int sortStart = totalLen - 1;
        int sortEnd = totalLen - 1;
        sortedArray.add(array[0]);
        for(int curPosi = 1; curPosi < totalLen; curPosi++){
            if(comparator.compare(array[curPosi], sortedArray.get(sortedArray.size() - 1)) >= 0){
                sortedArray.add(array[curPosi]);
            }else{
                sortEnd = curPosi;
                int insertPosi = Collections.binarySearch(sortedArray, array[curPosi], comparator);
                if(insertPosi >= 0){
                    System.out.println("1当前insert: " + insertPosi);
                    while (insertPosi < sortedArray.size() && sortedArray.get(insertPosi) == array[curPosi]){
                        insertPosi++;
                    }
                    sortStart = Math.min(sortStart, insertPosi); // 前面有这么个值, 那他往后的都需要重排, 注意相同值数量
                    System.out.println("1当前insert: " + insertPosi);
                    sortedArray.add(insertPosi, array[curPosi]);
                }else{
                    insertPosi = -insertPosi - 1;
                    sortStart = Math.min(sortStart, insertPosi);
                    System.out.println("2当前insert: " + insertPosi);
                    sortedArray.add(sortStart, array[curPosi]);
                }
            }
            System.out.println("添加之后: " + sortedArray);
        }
        if(sortStart == sortEnd) return new int[]{-1, -1};
        return new int[]{sortStart, sortEnd};
    }

    /**
     * 23, 复制, 排序, 找不一样的地方
     */
    public static int[] subSort2(int[] array) {
        if(array == null || array.length <= 2) return new int[]{-1, -1};
        int totalLen = array.length;
        int[] array2 = new int[totalLen];
        for(int i = 0; i < totalLen; i++){
            array2[i] = array[i];
        }
        if(array2[0] < array2[totalLen - 1]){
            Arrays.sort(array2); // 默认升序
        }else{
            Arrays.sort(array2);
            for(int i = 0; i < totalLen / 2; i++){
                int temp1 = array2[i];
                array2[i] = array2[totalLen - i - 1];
                array2[totalLen - i - 1] = temp1;
            }
        }
        int start = 0;
        while(start < totalLen && array[start] == array2[start])
            start++;
        if(start == totalLen)
            return new int[]{-1, -1};
        int end = totalLen - 1;
        while(end >= start && array[end] == array2[end]){
            end--;
        }
        return new int[]{start, end};
    }
    // 上面那个方法的体面版本
    public int[] subSort3(int[] array) {
        int[] clone = array.clone();
        Arrays.sort(clone);
        int left = -1;
        int right = -1;
        for (int i = 0; i < array.length; i++) {
            if (array[i] != clone[i]) {
                if (left == -1) {
                    left = i;
                }
                right = i;
            }
        }
        return new int[]{left, right};
    }

    /**
     * 从前往后, 可以通过最大值找到最后一个需要修改的数,
     * 从后往前可以找到第一个需要修改的数,
     * 也不算是双指针, 只是一种计算办法, 挺好
     */
    public int[] subSort4(int[] array) {
        if(array == null || array.length == 0) return new int[]{-1, -1};
        int last = -1, first = -1;
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        int len = array.length;

        for(int i = 0; i < len; i++){
            if(array[i] < max){
                last = i; // i肯定不在自己的位置上, 是最后一个需要修改的数
            }else{
                max = Math.max(max, array[i]);
            }

            if(array[len - 1 - i] > min){
                first = len - 1 - i;
            }else{
                min = Math.min(min, array[len - 1 - i]);
            }
        }
        return new int[] {first, last};
    }

}
